//
// Created by DengLibin on 2019/1/28 0028.
//
#include <stdio.h>
/**动态规划算法
 * 核心就是记住已经解决过的子问题的解
 * */

/**问题1：
 * 假定Serling 公司出售一段长度为i英寸的钢条价格为Pi(i=1,2,3....)
 * 价格表：
 * 钢条长度i  1, 2, 3, 4, 5,  6,  7,  8,  9,  10
 * 价格Pi    1, 5, 8, 9, 10, 17, 17, 20, 24, 30
 * 求 最优价格的切割方案。
 *
 公式：
最优价格   r(n) = max(Pn,r(1)+r(n-1), r(2)+r(n-2),...,r(n-1)+r1);(n>=1)
Pn:不切割时的价格

 公式变形： r(n) = max(Pi + r(n-i));(i从1到n)（n>=1）
 */

//钢条价格，下标表示长度，值表示价格
static int prices[11] = {0,1,5,8,9,10,17,17,20,24,30};

static int max_value(int x, int y){
    return x > y ? x : y;
}
/**
 * 求最优价 递归
 * @param n 钢条长度
 * @return
 */
static int getMaxPrice(int n){
    if(n == 0){
        return 0;
    }
    int maxPrice = 0;
    for(int i = 1; i <= n; i++){
        maxPrice = max_value(maxPrice, prices[i] + getMaxPrice(n-i));//上一层的最优解与下一层的最优解相关
    }
    return maxPrice;
}

/**
 * 问题2：
 * 在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，
 * 所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。
 * 假设 有4个人，过桥时间分别是：1 2 5 10，求 最小过桥时间
 * @return
 */
static  int min_value(int x, int y){
    return x < y ? x : y;
}
static int times[5]={0, 1, 2, 5, 10};//过桥时间（从小到达排序）
static int min_time(int i){
    if(i < 3){
        return times[i];//返回过桥时间最长的那个
    }
    //已过去i-1个人还剩下第i个人，则过桥时间为：min_time(i-1)+ times[1]+times[i]
    //已过去i-2个人还剩下第i个人，另一个人无所谓，则过桥时间：min_time(i-2)+times[1]+times[i]+2*times[2];(times[1]为第1号送手电筒过来，times[i]为剩下的两人过桥，2*times[2]表示第2号送手电过来再和第1号过去)
    return min_value(min_time(i-1)+ times[1]+times[i], min_time(i-2)+times[1]+times[i]+2*times[2]);
}


int main3  (){
    //printf("最优价格:%d\n",getMaxPrice(4));
    printf("最短过桥时间:%d\n",min_time(4));
}



